<!DOCTYPE HTML>
<html lang="zh-CN">


<head><meta name="generator" content="Hexo 3.9.0">
    <meta charset="utf-8">
    <meta name="keywords" content="十大经典排序算法(附动画及代码), 被动学习">
    <meta name="baidu-site-verification" content="fmlEuI34ir">
    <meta name="google-site-verification" content="yCy2azpds5XSuGZvis6OuA-XIGF5GuGpYRAaGfD6o48">
    <meta name="360-site-verification" content="b7c11a830ef90fd1464ad6206bb7b6e7">
    <meta name="description" content="各个算法的时空复杂度及稳定性：
稳定：如果a原本在b前面，且a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，且a=b，排序之后 a 可能会出现在 b 的后面。


一、冒泡排序（Bubble Sort）1、原理​    基">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=no">
    <meta name="renderer" content="webkit|ie-stand|ie-comp">
    <meta name="mobile-web-app-capable" content="yes">
    <meta name="format-detection" content="telephone=no">
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black-translucent">
    <title>十大经典排序算法(附动画及代码) | Shawlon`s Blog</title>
    <link rel="icon" type="image/jpeg" href="https://cdn.jsdelivr.net/gh/MUYIio/CDN@1.2/Images/avatars/favicon.jpg">

    <link rel="stylesheet" type="text/css" href="/libs/awesome/css/font-awesome.min.css">
    <link rel="stylesheet" type="text/css" href="/libs/materialize/materialize.min.css">
    <link rel="stylesheet" type="text/css" href="/libs/aos/aos.css">
    <link rel="stylesheet" type="text/css" href="/libs/animate/animate.min.css">
    <link rel="stylesheet" type="text/css" href="/libs/lightGallery/css/lightgallery.min.css">
    <link rel="stylesheet" type="text/css" href="/css/matery.css">
    <link rel="stylesheet" type="text/css" href="/css/my.css">
    <style type="text/css">
        
    </style>

    <script src="/libs/jquery/jquery-2.2.0.min.js"></script>
    <script src="https://sdk.jinrishici.com/v2/browser/jinrishici.js" charset="utf-8"></script>

    <script>
    var _hmt = _hmt || [];
    (function() {
    var hm = document.createElement("script");
    hm.src = "https://hm.baidu.com/hm.js?4d1d73af45a62734730491a6b6c41da4";
    var s = document.getElementsByTagName("script")[0]; 
    s.parentNode.insertBefore(hm, s);
    })();
   </script>


    <script>(function (i, s, o, g, r, a, m) {
        i['DaoVoiceObject'] = r;
        i[r] = i[r] ||
          function () {
            (i[r].q = i[r].q || []).push(arguments);
          };
        i[r].l = 1 * new Date();
        a = s.createElement(o);
        m = s.getElementsByTagName(o)[0];
        a.async = 1;
        a.src = g;
        a.charset = 'utf-8';
        m.parentNode.insertBefore(a, m);
      })(window, document, 'script', ('https:' === document.location.protocol ? 'https:' : 'http:') + "//widget.daovoice.io/widget/0fcc9bf7.js", 'daovoice');
      daovoice('init', {
        app_id: "0fcc9bf7",
      });
      daovoice('update');
    </script>
  
  


    
        <script>
            (function(){
                var bp = document.createElement('script');
                var curProtocol = window.location.protocol.split(':')[0];
                if (curProtocol === 'https') {
                    bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';        
                }
                else {
                    bp.src = 'http://push.zhanzhang.baidu.com/push.js';
                }
                var s = document.getElementsByTagName("script")[0];
                s.parentNode.insertBefore(bp, s);
            })();
        </script>
    

    <script>
        (function(){
        var src = "https://jspassport.ssl.qhimg.com/11.0.1.js?d182b3f28525f2db83acfaaf6e696dba";
        document.write('<script src="' + src + '" id="sozz"><\/script>');
        })();
    </script>

    <meta name="baidu-site-verification" content="code-FwB5xSTmVO">




<style type="text/css" lang="css">
    #loading-container{
        position: fixed;
        top: 0;
        left: 0;
        min-height: 100vh;
        width: 100vw;
        z-index: 9999;
        display: flex;
        flex-direction: column;
        justify-content: center;
        align-items: center;
        background: #FFF;
        text-align: center;
        /* loaderҳ����ʧ���ý����ķ�ʽ*/
        -webkit-transition: opacity 1s ease;
        -moz-transition: opacity 1s ease;
        -o-transition: opacity 1s ease;
        transition: opacity 1s ease;
    }
    .loading-image{
        width: 120px;
        height: 50px;
        transform: translate(-50%);
    }

    .loading-image div:nth-child(2) {
        -webkit-animation: pacman-balls 1s linear 0s infinite;
        animation: pacman-balls 1s linear 0s infinite
    }

    .loading-image div:nth-child(3) {
        -webkit-animation: pacman-balls 1s linear .33s infinite;
        animation: pacman-balls 1s linear .33s infinite
    }

    .loading-image div:nth-child(4) {
        -webkit-animation: pacman-balls 1s linear .66s infinite;
        animation: pacman-balls 1s linear .66s infinite
    }

    .loading-image div:nth-child(5) {
        -webkit-animation: pacman-balls 1s linear .99s infinite;
        animation: pacman-balls 1s linear .99s infinite
    }

   .loading-image div:first-of-type {
        width: 0;
        height: 0;
        border: 25px solid #49b1f5;
        border-right-color: transparent;
        border-radius: 25px;
        -webkit-animation: rotate_pacman_half_up .5s 0s infinite;
        animation: rotate_pacman_half_up .5s 0s infinite;
    }
    .loading-image div:nth-child(2) {
        width: 0;
        height: 0;
        border: 25px solid #49b1f5;
        border-right-color: transparent;
        border-radius: 25px;
        -webkit-animation: rotate_pacman_half_down .5s 0s infinite;
        animation: rotate_pacman_half_down .5s 0s infinite;
        margin-top: -50px;
    }
    @-webkit-keyframes rotate_pacman_half_up {0% {transform: rotate(270deg)}50% {transform: rotate(1turn)}to {transform: rotate(270deg)}}

    @keyframes rotate_pacman_half_up {0% {transform: rotate(270deg)}50% {transform: rotate(1turn)}to {transform: rotate(270deg)}}

    @-webkit-keyframes rotate_pacman_half_down {0% {transform: rotate(90deg)}50% {transform: rotate(0deg)}to {transform: rotate(90deg)}}

    @keyframes rotate_pacman_half_down {0% {transform: rotate(90deg)}50% {transform: rotate(0deg)}to {transform: rotate(90deg)}}

    @-webkit-keyframes pacman-balls {75% {opacity: .7}to {transform: translate(-100px, -6.25px)}}

    @keyframes pacman-balls {75% {opacity: .7}to {transform: translate(-100px, -6.25px)}}


    .loading-image div:nth-child(3),
    .loading-image div:nth-child(4),
    .loading-image div:nth-child(5),
    .loading-image div:nth-child(6){
        background-color: #49b1f5;
        width: 15px;
        height: 15px;
        border-radius: 100%;
        margin: 2px;
        width: 10px;
        height: 10px;
        position: absolute;
        transform: translateY(-6.25px);
        top: 25px;
        left: 100px;
    }
    .loading-text{
        margin-bottom: 20vh;
        text-align: center;
        color: #2c3e50;
        font-size: 2rem;
        box-sizing: border-box;
        padding: 0 10px;
        text-shadow: 0 2px 10px rgba(0,0,0,0.2);
    }
    @media only screen and (max-width: 500px) {
         .loading-text{
            font-size: 1.5rem;
         }
    }
    .fadeout {
        opacity: 0;
        filter: alpha(opacity=0);
    }
    /* logo���ֶ��� */
    @-webkit-keyframes fadeInDown{0%{opacity:0;-webkit-transform:translate3d(0,-100%,0);transform:translate3d(0,-100%,0)}100%{opacity:1;-webkit-transform:none;transform:none}}
    @keyframes fadeInDown{0%{opacity:0;-webkit-transform:translate3d(0,-100%,0);}}
 </style>
 <script>
(function () {
    const loaded = function(){
       setTimeout(function(){
            const loader = document.getElementById("loading-container");
            loader.className="fadeout" ;//ʹ�ý����ķ�������loading page
            // document.getElementById("body-wrap").style.display="flex";
            setTimeout(function(){
                loader.style.display="none";
            },1000); 
        },1000);//ǿ����ʾloading page 1s  
    };
    loaded();
})()
 </script><link rel="stylesheet" href="/css/prism-tomorrow.css" type="text/css">
<link rel="stylesheet" href="/css/prism-line-numbers.css" type="text/css"><style type="text/css" lang="css">
    #loading-container{
        position: fixed;
        top: 0;
        left: 0;
        min-height: 100vh;
        width: 100vw;
        z-index: 9999;
        display: flex;
        flex-direction: column;
        justify-content: center;
        align-items: center;
        background: #FFF;
        text-align: center;
        /* loaderҳ����ʧ���ý����ķ�ʽ*/
        -webkit-transition: opacity 1s ease;
        -moz-transition: opacity 1s ease;
        -o-transition: opacity 1s ease;
        transition: opacity 1s ease;
    }
    .loading-image{
        width: 120px;
        height: 50px;
        transform: translate(-50%);
    }

    .loading-image div:nth-child(2) {
        -webkit-animation: pacman-balls 1s linear 0s infinite;
        animation: pacman-balls 1s linear 0s infinite
    }

    .loading-image div:nth-child(3) {
        -webkit-animation: pacman-balls 1s linear .33s infinite;
        animation: pacman-balls 1s linear .33s infinite
    }

    .loading-image div:nth-child(4) {
        -webkit-animation: pacman-balls 1s linear .66s infinite;
        animation: pacman-balls 1s linear .66s infinite
    }

    .loading-image div:nth-child(5) {
        -webkit-animation: pacman-balls 1s linear .99s infinite;
        animation: pacman-balls 1s linear .99s infinite
    }

   .loading-image div:first-of-type {
        width: 0;
        height: 0;
        border: 25px solid #49b1f5;
        border-right-color: transparent;
        border-radius: 25px;
        -webkit-animation: rotate_pacman_half_up .5s 0s infinite;
        animation: rotate_pacman_half_up .5s 0s infinite;
    }
    .loading-image div:nth-child(2) {
        width: 0;
        height: 0;
        border: 25px solid #49b1f5;
        border-right-color: transparent;
        border-radius: 25px;
        -webkit-animation: rotate_pacman_half_down .5s 0s infinite;
        animation: rotate_pacman_half_down .5s 0s infinite;
        margin-top: -50px;
    }
    @-webkit-keyframes rotate_pacman_half_up {0% {transform: rotate(270deg)}50% {transform: rotate(1turn)}to {transform: rotate(270deg)}}

    @keyframes rotate_pacman_half_up {0% {transform: rotate(270deg)}50% {transform: rotate(1turn)}to {transform: rotate(270deg)}}

    @-webkit-keyframes rotate_pacman_half_down {0% {transform: rotate(90deg)}50% {transform: rotate(0deg)}to {transform: rotate(90deg)}}

    @keyframes rotate_pacman_half_down {0% {transform: rotate(90deg)}50% {transform: rotate(0deg)}to {transform: rotate(90deg)}}

    @-webkit-keyframes pacman-balls {75% {opacity: .7}to {transform: translate(-100px, -6.25px)}}

    @keyframes pacman-balls {75% {opacity: .7}to {transform: translate(-100px, -6.25px)}}


    .loading-image div:nth-child(3),
    .loading-image div:nth-child(4),
    .loading-image div:nth-child(5),
    .loading-image div:nth-child(6){
        background-color: #49b1f5;
        width: 15px;
        height: 15px;
        border-radius: 100%;
        margin: 2px;
        width: 10px;
        height: 10px;
        position: absolute;
        transform: translateY(-6.25px);
        top: 25px;
        left: 100px;
    }
    .loading-text{
        margin-bottom: 20vh;
        text-align: center;
        color: #2c3e50;
        font-size: 2rem;
        box-sizing: border-box;
        padding: 0 10px;
        text-shadow: 0 2px 10px rgba(0,0,0,0.2);
    }
    @media only screen and (max-width: 500px) {
         .loading-text{
            font-size: 1.5rem;
         }
    }
    .fadeout {
        opacity: 0;
        filter: alpha(opacity=0);
    }
    /* logo���ֶ��� */
    @-webkit-keyframes fadeInDown{0%{opacity:0;-webkit-transform:translate3d(0,-100%,0);transform:translate3d(0,-100%,0)}100%{opacity:1;-webkit-transform:none;transform:none}}
    @keyframes fadeInDown{0%{opacity:0;-webkit-transform:translate3d(0,-100%,0);}}
 </style>
 <script>
(function () {
    const loaded = function(){
       setTimeout(function(){
            const loader = document.getElementById("loading-container");
            loader.className="fadeout" ;//ʹ�ý����ķ�������loading page
            // document.getElementById("body-wrap").style.display="flex";
            setTimeout(function(){
                loader.style.display="none";
            },1000); 
        },1000);//ǿ����ʾloading page 1s  
    };
    loaded();
})()
 </script></head>


 <div id="loading-container">
     <p class="loading-text"></p> 
     <div class="loading-image">
         <div></div>
         <div></div>
         <div></div>
         <div></div> 
         <div></div>
     </div>
 </div><body>

    <header class="navbar-fixed">
    <nav id="headNav" class="bg-color nav-transparent">
        <div id="navContainer" class="nav-wrapper container">
            <div class="brand-logo">
                <a href="/" class="waves-effect waves-light">
                    
                    <img src="https://cdn.jsdelivr.net/gh/MUYIio/CDN@1.2/Images/logo.png" class="logo-img" alt="LOGO">
                    
                    <span class="logo-span">Shawlon`s Blog</span>
                </a>
            </div>
            

<a href="#" data-target="mobile-nav" class="sidenav-trigger button-collapse"><i class="fa fa-navicon"></i></a>
<ul class="right">
    
    <li class="hide-on-med-and-down">
        <a href="/" class="waves-effect waves-light">
            
            <span>首页</span>
        </a>
    </li>
    
    <li class="hide-on-med-and-down">
        <a href="/tags" class="waves-effect waves-light">
            
            <span>标签</span>
        </a>
    </li>
    
    <li class="hide-on-med-and-down">
        <a href="/categories" class="waves-effect waves-light">
            
            <span>分类</span>
        </a>
    </li>
    
    <li class="hide-on-med-and-down">
        <a href="/archives" class="waves-effect waves-light">
            
            <span>归档</span>
        </a>
    </li>
    
    <li class="hide-on-med-and-down">
        <a href="/about" class="waves-effect waves-light">
            
            <span>关于</span>
        </a>
    </li>
    
    <li class="hide-on-med-and-down">
        <a href="/friends" class="waves-effect waves-light">
            
            <span>友情链接</span>
        </a>
    </li>
    
    <li class="hide-on-med-and-down">
        <a href="/contact" class="waves-effect waves-light">
            
            <span>留言板</span>
        </a>
    </li>
    
    <li>
        <a href="#searchModal" class="modal-trigger waves-effect waves-light">
            <i id="searchIcon" class="fa fa-search" title="搜索"></i>
        </a>
    </li>
</ul>

<div id="mobile-nav" class="side-nav sidenav">

    <div class="mobile-head bg-color">
        
        <img src="https://cdn.jsdelivr.net/gh/MUYIio/CDN@1.2/Images/logo.png" class="logo-img circle responsive-img">
        
        <div class="logo-name">Shawlon`s Blog</div>
        <div class="logo-desc">
            
            C++ | LeetCode | Algorithm
            
        </div>
    </div>

    

    <ul class="menu-list mobile-menu-list">
        
        <li>
            <a href="/" class="waves-effect waves-light">
                
                <i class="fa fa-fw fa-link"></i>
                
                首页
            </a>
        </li>
        
        <li>
            <a href="/tags" class="waves-effect waves-light">
                
                <i class="fa fa-fw fa-link"></i>
                
                标签
            </a>
        </li>
        
        <li>
            <a href="/categories" class="waves-effect waves-light">
                
                <i class="fa fa-fw fa-link"></i>
                
                分类
            </a>
        </li>
        
        <li>
            <a href="/archives" class="waves-effect waves-light">
                
                <i class="fa fa-fw fa-link"></i>
                
                归档
            </a>
        </li>
        
        <li>
            <a href="/about" class="waves-effect waves-light">
                
                <i class="fa fa-fw fa-link"></i>
                
                关于
            </a>
        </li>
        
        <li>
            <a href="/friends" class="waves-effect waves-light">
                
                <i class="fa fa-fw fa-link"></i>
                
                友情链接
            </a>
        </li>
        
        <li>
            <a href="/contact" class="waves-effect waves-light">
                
                <i class="fa fa-fw fa-link"></i>
                
                留言板
            </a>
        </li>
        
        
        <li><div class="divider"></div></li>
        <li>
            <a href="https://github.com/muyiio" class="waves-effect waves-light" target="_blank">
                <i class="fa fa-github-square fa-fw"></i>Fork Me
            </a>
        </li>
        
    </ul>
</div>

        </div>

        
            <style>
    .nav-transparent .github-corner {
        display: none !important;
    }

    .github-corner {
        position: absolute;
        z-index: 10;
        top: 0;
        right: 0;
        border: 0;
        transform: scale(1.1);
    }

    .github-corner svg {
        color: #0f9d58;
        fill: #fff;
        height: 64px;
        width: 64px;
    }

    .github-corner:hover .octo-arm {
        animation: a 0.56s ease-in-out;
    }

    .github-corner .octo-arm {
        animation: none;
    }

    @keyframes a {
        0%,
        to {
            transform: rotate(0);
        }
        20%,
        60% {
            transform: rotate(-25deg);
        }
        40%,
        80% {
            transform: rotate(10deg);
        }
    }
</style>

<a href="https://github.com/muyiio" class="github-corner tooltipped hide-on-med-and-down" target="_blank"
   data-tooltip="Fork Me" data-position="left" data-delay="50">
    <svg viewBox="0 0 250 250" aria-hidden="true">
        <path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"></path>
        <path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2"
              fill="currentColor" style="transform-origin: 130px 106px;" class="octo-arm"></path>
        <path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z"
              fill="currentColor" class="octo-body"></path>
    </svg>
</a>
        
    </nav>

</header>

    
<script src="/libs/cryptojs/crypto-js.min.js"></script>
<script>
    (function() {
        let pwd = '';
        if (pwd && pwd.length > 0) {
            if (pwd !== CryptoJS.SHA256(prompt('请输入访问本文章的密码')).toString(CryptoJS.enc.Hex)) {
                alert('密码错误，将返回主页！');
                location.href = '/';
            }
        }
    })();
</script>




<div class="bg-cover pd-header post-cover" style="background-image: url('https://cdn.jsdelivr.net/gh/MUYIio/CDN@1.2/Images/featureimages/24.jpg')">
    <div class="container">
        <div class="row">
            <div class="col s12 m12 l12">
                <div class="brand">
                    <div class="description center-align post-title">
                        十大经典排序算法(附动画及代码)
                    </div>
                </div>
            </div>
        </div>
    </div>
</div>



<main class="post-container content">

    
    <link rel="stylesheet" href="/libs/tocbot/tocbot.css">
<style>
    #articleContent h1::before,
    #articleContent h2::before,
    #articleContent h3::before,
    #articleContent h4::before,
    #articleContent h5::before,
    #articleContent h6::before {
        display: block;
        content: " ";
        height: 100px;
        margin-top: -100px;
        visibility: hidden;
    }

    #articleContent :focus {
        outline: none;
    }

    .toc-fixed {
        position: fixed;
        top: 64px;
    }

    .toc-widget {
        padding-left: 20px;
    }

    .toc-widget .toc-title {
        margin: 35px 0 15px 0;
        padding-left: 17px;
        font-size: 1.5rem;
        font-weight: bold;
        line-height: 1.5rem;
    }

    .toc-widget ol {
        padding: 0;
        list-style: none;
    }

    #toc-content ol {
        padding-left: 10px;
    }

    #toc-content ol li {
        padding-left: 10px;
    }

    #toc-content .toc-link:hover {
        color: #42b983;
        font-weight: 700;
        text-decoration: underline;
    }

    #toc-content .toc-link::before {
        background-color: transparent;
        max-height: 25px;
    }

    #toc-content .is-active-link {
        color: #42b983;
    }

    #toc-content .is-active-link::before {
        background-color: #42b983;
    }

    #floating-toc-btn {
        position: fixed;
        right: 20px;
        bottom: 76px;
        padding-top: 15px;
        margin-bottom: 0;
        z-index: 998;
    }

    #floating-toc-btn .btn-floating {
        width: 48px;
        height: 48px;
    }

    #floating-toc-btn .btn-floating i {
        line-height: 48px;
        font-size: 1.4rem;
    }
</style>
<div class="row">
    <div id="main-content" class="col s12 m12 l9">
        <!-- 文章内容详情 -->
<div id="artDetail">
    <div class="card">
        <div class="card-content article-info">
            <div class="row tag-cate">
                <div class="col s7">
                    
                    <div class="article-tag">
                        
                        <a href="/tags/排序/" target="_blank">
                            <span class="chip bg-color">排序</span>
                        </a>
                        
                    </div>
                    
                </div>
                <div class="col s5 right-align">
                    
                    <div class="post-cate">
                        <i class="fa fa-bookmark fa-fw icon-category"></i>
                        
                        <a href="/categories/算法/" class="post-category" target="_blank">
                            算法
                        </a>
                        
                        <a href="/categories/算法/C/" class="post-category" target="_blank">
                            C++
                        </a>
                        
                    </div>
                    
                </div>
            </div>

            <div class="post-info">
                <div class="post-date info-break-policy">
                    <i class="fa fa-calendar-minus-o fa-fw"></i>发布日期:&nbsp;&nbsp;
                    2021-12-14
                </div>

                <div class="post-author info-break-policy">
                    <i class="fa fa-user-o fa-fw"></i>作者:&nbsp;&nbsp;
                    
                    Tyzhao
                    
                </div>

                
                
                <div class="info-break-policy">
                    <i class="fa fa-file-word-o fa-fw"></i>文章字数:&nbsp;&nbsp;
                    2.5k
                </div>
                

                
                <div class="info-break-policy">
                    <i class="fa fa-clock-o fa-fw"></i>阅读时长:&nbsp;&nbsp;
                    9 分
                </div>
                
                

                
                <div id="busuanzi_container_page_pv" class="info-break-policy">
                    <i class="fa fa-eye fa-fw"></i>阅读次数:&nbsp;&nbsp;
                    <span id="busuanzi_value_page_pv"></span>
                </div>
                
            </div>
        </div>
        <hr class="clearfix">
        <div class="card-content article-card-content">
            <div id="articleContent">
                <h2 id="各个算法的时空复杂度及稳定性："><a href="#各个算法的时空复杂度及稳定性：" class="headerlink" title="各个算法的时空复杂度及稳定性："></a>各个算法的时空复杂度及稳定性：</h2><ul>
<li><strong>稳定</strong>：如果a原本在b前面，且a=b，排序之后a仍然在b的前面。</li>
<li><strong>不稳定</strong>：如果a原本在b的前面，且a=b，排序之后 a 可能会出现在 b 的后面。</li>
</ul>
<p><img src="https://cdn.jsdelivr.net/gh/MUYIio/CDN@2.2/Images/posts/qSort/14.png" alt></p>
<h2 id="一、冒泡排序（Bubble-Sort）"><a href="#一、冒泡排序（Bubble-Sort）" class="headerlink" title="一、冒泡排序（Bubble Sort）"></a>一、冒泡排序（Bubble Sort）</h2><h3 id="1、原理"><a href="#1、原理" class="headerlink" title="1、原理"></a>1、原理</h3><p>​    基本思想：通过无序区中相邻元素关键字间的比较和位置的交换，使关键字最小的元素像气泡一样浮到最顶部；接着对剩下的元素排序，使得第二小的元素到达顶部，同样的方法直到所有元素排序完成。</p>
<h3 id="2、步骤"><a href="#2、步骤" class="headerlink" title="2、步骤"></a>2、步骤</h3><ul>
<li><strong>①</strong> 比较相邻的元素。如果第一个比第二个大，就交换它们两个；</li>
<li><strong>②</strong> 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；</li>
<li><strong>③</strong> 针对所有的元素重复步骤 <strong>①</strong> ~ <strong>②</strong>，除了最后一个元素，直到排序完成。</li>
</ul>
<h3 id="3、动画演示"><a href="#3、动画演示" class="headerlink" title="3、动画演示"></a>3、动画演示</h3><p><img src="https://cdn.jsdelivr.net/gh/MUYIio/CDN@2.1/Images/posts/qSort/1.gif" alt></p>
<h3 id="4、代码实现"><a href="#4、代码实现" class="headerlink" title="4、代码实现"></a>4、代码实现</h3><pre class="line-numbers language-c++"><code class="language-c++">void bubble_sort()
{
    for (int i = n-1; i >= 1; i -- )
    {
        bool flag = true;
        for (int j = 1; j <= i; j ++ )
            if (a[j-1] > a[j])
            {
                swap(a[j-1], a[j]);
                flag = false;
            }
        if (flag) return;
    }
}<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="二、选择排序（Selection-Sort）"><a href="#二、选择排序（Selection-Sort）" class="headerlink" title="二、选择排序（Selection Sort）"></a>二、选择排序（Selection Sort）</h2><h3 id="1、原理-1"><a href="#1、原理-1" class="headerlink" title="1、原理"></a>1、原理</h3><p>​    选择排序是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。</p>
<h3 id="2、步骤-1"><a href="#2、步骤-1" class="headerlink" title="2、步骤"></a>2、步骤</h3><p>n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：</p>
<ul>
<li>初始状态：无序区为<code>R[1..n]</code>，有序区为空；</li>
<li>第i趟排序<code>(i=1,2,3…n-1)</code>开始时，当前有序区和无序区分别为<code>R[1..i-1]</code>和<code>R(i..n）</code>。该趟排序从当前无序区中-选出关键字最小的记录 <code>R[k]</code>，将它与无序区的第1个记录R交换，使<code>R[1..i]</code>和<code>R[i+1..n)</code>分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；</li>
<li><code>n-1</code>趟结束，数组有序化了。</li>
</ul>
<h3 id="3、动画演示-1"><a href="#3、动画演示-1" class="headerlink" title="3、动画演示"></a>3、动画演示</h3><p><img src="https://cdn.jsdelivr.net/gh/MUYIio/CDN@2.1/Images/posts/qSort/2.gif" alt></p>
<h3 id="4、代码实现-1"><a href="#4、代码实现-1" class="headerlink" title="4、代码实现"></a>4、代码实现</h3><pre class="line-numbers language-c++"><code class="language-c++">void select_sort()
{
    for (int i = 0; i < n; i ++ )
    {
        int k = i;
        for (int j = i+1; j < n; j ++ )
        {
            if (a[j] < a[k])
                k = j;
        }
        swap(a[i], a[k]);
    }
}<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="三、插入排序（Insertion-Sort）"><a href="#三、插入排序（Insertion-Sort）" class="headerlink" title="三、插入排序（Insertion Sort）"></a>三、插入排序（Insertion Sort）</h2><h3 id="1、原理-2"><a href="#1、原理-2" class="headerlink" title="1、原理"></a>1、原理</h3><p>  这里主要针对直接插入排序。将元素与已经排序的有序序列比较，找到对应的位置插入。</p>
<h3 id="2、步骤-2"><a href="#2、步骤-2" class="headerlink" title="2、步骤"></a>2、步骤</h3><ul>
<li>① 从第一个元素开始，该元素可以认为已经被排序；</li>
<li>② 取出下一个元素，在已经排序的元素序列中从后向前扫描；</li>
<li>③ 如果该元素（已排序）大于新元素，将该元素移到下一位置；</li>
<li>④ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；</li>
<li>⑤ 将新元素插入到该位置后；</li>
<li>⑥ 重复步骤2~5。</li>
</ul>
<h3 id="3、动画演示-2"><a href="#3、动画演示-2" class="headerlink" title="3、动画演示"></a>3、动画演示</h3><p><img src="https://cdn.jsdelivr.net/gh/MUYIio/CDN@2.1/Images/posts/qSort/3.gif" alt></p>
<h3 id="4、代码实现-2"><a href="#4、代码实现-2" class="headerlink" title="4、代码实现"></a>4、代码实现</h3><pre class="line-numbers language-c++"><code class="language-c++">void insert_sort()
{
    for (int i = 1; i < n; i ++ )
    {
        int x = a[i];
        int j = i-1;

        while (j >= 0 && x < a[j])
        {
            a[j+1] = a[j];
            j -- ;
        }
        a[j+1] = x;
    }
}<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="四、快速排序（Quick-Sort）"><a href="#四、快速排序（Quick-Sort）" class="headerlink" title="四、快速排序（Quick Sort）"></a>四、快速排序（Quick Sort）</h2><h3 id="1、原理-3"><a href="#1、原理-3" class="headerlink" title="1、原理"></a>1、原理</h3><p>​    一般选择将待排序序列分为两个序列，正中间的那个数作为关键字，然后两个指针一个从头到关键字遍历，遇到大于（小于）关键字的元素就停下来，另一个指针从尾到关键字遍历，遇到小于（大于）关键字的元素停下来，交换两个指针的元素完成排序；将序列递归分治按照前面的原理排序，直到序列有序。</p>
<h3 id="2、步骤-3"><a href="#2、步骤-3" class="headerlink" title="2、步骤"></a>2、步骤</h3><p>快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：</p>
<ul>
<li>选取基准元素（pivot）</li>
<li>划分，根据选取的pivot将数组划分成小于pivot的部分和大于pivot的部分</li>
<li>递归求解小于pivot和大于pivot的部分</li>
</ul>
<p>基准元素可以选择第一个元素或者最后一个元素即 Lomuto Partition Scheme，但是这样划分成两部分的时候有一部分是空的，这样可能造成死循环；从中间划分可以保证两部分都不为空，即 Hoare Partition Scheme。</p>
<h3 id="3、动画演示-3"><a href="#3、动画演示-3" class="headerlink" title="3、动画演示"></a>3、动画演示</h3><p><img src="https://cdn.jsdelivr.net/gh/MUYIio/CDN@2.1/Images/posts/qSort/4.gif" alt></p>
<h3 id="4、代码实现-3"><a href="#4、代码实现-3" class="headerlink" title="4、代码实现"></a>4、代码实现</h3><pre class="line-numbers language-c++"><code class="language-c++">void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p><strong>快速排序的边界问题</strong></p>
<p>快排属于分治算法，最怕的就是 <code>n</code>分成<code>0</code>和<code>n</code>，或 <code>n</code>分成<code>n</code>和<code>0</code>,导致死循环。</p>
<ol>
<li><p><strong>以<code>j</code>为划分时，<code>x</code>不能选<code>q[r]</code> (若以<code>i</code>为划分,则<code>x</code>不能选<code>q[l]</code>)</strong></p>
<p>​    假设 <code>x = q[r]</code></p>
<p>​    关键句子<code>quick_sort(q, l, j), quick_sort(q, j + 1, r);</code></p>
<p>​    由于j的最小值是l,所以<code>q[j+1..r]</code>不会造成无限划分</p>
<p>​    但<code>q[l..j]（即quick_sort(q, l, j)）</code>却可能造成无限划分，因为j可能为r</p>
<p>​    举例来说，若<code>x</code>选为<code>q[r]</code>，数组中<code>q[l..r-1] &lt; x</code>,</p>
<p>​    那么这一轮循环结束时<code>i = r, j = r</code>，显然会造成无限划分</p>
</li>
<li><p><strong>do i++; while(q[i] &lt; x)和do j–; while(q[j] &gt; x)不能用q[i] &lt;= x 和 q[j] &gt;= x</strong></p>
<p>​    假设<code>q[l..r]</code>全相等</p>
<p>​    则执行完<code>do i++; while(q[i] &lt;= x);</code>之后，<code>i</code>会自增到<code>r+1</code></p>
<p>​    然后继续执行<code>q[i] &lt;= x</code> 判断条件，造成数组下标越界(但这貌似不会报错)</p>
<p>​    并且如果之后的<code>q[i] &lt;= x</code> (此时i &gt; r) 条件也不幸成立，</p>
<p>​    就会造成一直循环下去(亲身实验)，造成内存超限(Memory Limit Exceeded)</p>
</li>
<li><p><strong><code>if(i &lt; j) swap(q[i], q[j])</code>能否使用 <code>i &lt;= j</code></strong></p>
<p>​    可以使用<code>if(i &lt;= j) swap(q[i], q[j])</code>;</p>
<p>​    因为 <code>i = j</code> 时，交换一下<code>q[i],q[j]</code> 无影响，因为马上就会跳出循环了</p>
</li>
<li><p><strong>最后一句能否改用quick_sort(q, l, j-1), quick_sort(q, j, r)作为划分(用i做划分时也是同样的道理,)</strong></p>
<p>​    不能</p>
<p>​    根据之前的证明，最后一轮循环可以得到这些结论</p>
<p>​    <code>j &lt;= i</code> 和 <code>q[l..i-1] &lt;= x</code>, <code>q[i] &gt;= x</code> 和 <code>q[j+1..r] &gt;= x</code>, <code>q[j] &lt;= x</code></p>
<p>​    所以，<code>q[l..j-1] &lt;= x</code> 是显然成立的，</p>
<p>​    但<code>quick_sort(q, j, r)</code>中的<code>q[j]</code> 却是 <code>q[j] &lt;= x</code>，这不符合快排的要求</p>
<p>​    另外一点，注意<code>quick_sort(q, l, j-1), quick_sort(q, j, r)</code>可能会造成无线划分</p>
<p>​    当x选为q[l]时会造成无限划分，报错为(MLE),</p>
<p>​    如果手动改为 <code>x = q[r]</code>,可以避免无限划分</p>
<p>​    但是上面所说的<code>q[j] &lt;= x</code> 的问题依然不能解决，这会造成 WA (Wrong Answer)</p>
</li>
<li><p><strong><code>j</code>的取值范围为<code>[l..r-1]</code></strong></p>
<p>​    <strong>证明:</strong></p>
<p>​    假设 <code>j</code> 最终的值为 <code>r</code> ,说明只有一轮循环(两轮的话 <code>j</code> 至少会自减两次)</p>
<p>​    说明<code>q[r] &lt;= x</code> (因为要跳出do-while循环)</p>
<p>​    说明 <code>i &gt;= r(while循环的结束条件)</code>, i 为 r 或 r + 1(必不可能成立)</p>
<p>​    说明 <code>i</code> 自增到了 <code>r</code> , 说明 <code>q[r] &gt;= x</code> 和 <code>q[l..r-1] &lt; x</code>,</p>
<p>​    得出 <code>q[r] = x</code> 和 <code>q[l..r-1] &lt; x</code> 的结论,但这与 <code>x = q[l + r &gt;&gt; 1]</code>矛盾</p>
<p>​    反证法得出 <code>j &lt; r</code></p>
<p>​    假设 <code>j</code> 可能小于 <code>l</code> 说明 <code>q[l..r] &gt; x</code> ,矛盾</p>
<p>​    反证法得出 <code>j &gt;= l</code></p>
</li>
</ol>
<p><strong>所以 <code>j</code>的取值范围为<code>[l..r-1]</code>,不会造成无限划分和数组越界。</strong></p>
<h2 id="五、希尔排序（Shell-Sort）"><a href="#五、希尔排序（Shell-Sort）" class="headerlink" title="五、希尔排序（Shell Sort）"></a>五、希尔排序（Shell Sort）</h2><h3 id="1、原理-4"><a href="#1、原理-4" class="headerlink" title="1、原理"></a>1、原理</h3><p>​    希尔排序又叫<strong>缩小增量排序</strong>，也是一种插入排序方法（通常快于直接插入法），具体做法是将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序；</p>
<h3 id="2、步骤-4"><a href="#2、步骤-4" class="headerlink" title="2、步骤"></a>2、步骤</h3><ul>
<li>1.先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作…</li>
<li>2.当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。</li>
</ul>
<p>对于增量的选定无一定论，但最后一个增量必须等于1，也就是说，每趟后一个增量是前一个增量的1/2。</p>
<h3 id="3、动画演示-4"><a href="#3、动画演示-4" class="headerlink" title="3、动画演示"></a>3、动画演示</h3><p><img src="https://cdn.jsdelivr.net/gh/MUYIio/CDN@2.1/Images/posts/qSort/5.gif" alt></p>
<h3 id="4、代码实现-4"><a href="#4、代码实现-4" class="headerlink" title="4、代码实现"></a>4、代码实现</h3><pre class="line-numbers language-c++"><code class="language-c++">void shell_sort()
{
    for (int gap = n >> 1; gap; gap >>= 1)
    {
        for (int i = gap; i < n; i ++ )
        {
            int x = a[i];
            int j;
            for (j = i; j >= gap && a[j-gap] > x; j -= gap)
                a[j] = a[j-gap];
            a[j] = x;
        }
    }
}
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="六、归并排序（Merge-Sort）"><a href="#六、归并排序（Merge-Sort）" class="headerlink" title="六、归并排序（Merge Sort）"></a>六、归并排序（Merge Sort）</h2><h3 id="1、原理-5"><a href="#1、原理-5" class="headerlink" title="1、原理"></a>1、原理</h3><p>   归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。</p>
<h3 id="2、步骤-5"><a href="#2、步骤-5" class="headerlink" title="2、步骤"></a>2、步骤</h3><ul>
<li>把长度为n的输入序列分成两个长度为n/2的子序列；</li>
<li>对这两个子序列分别采用归并排序；</li>
<li>将两个排序好的子序列合并成一个最终的排序序列</li>
</ul>
<h3 id="3、动画演示-5"><a href="#3、动画演示-5" class="headerlink" title="3、动画演示"></a>3、动画演示</h3><p><img src="https://cdn.jsdelivr.net/gh/MUYIio/CDN@2.1/Images/posts/qSort/6.gif" alt></p>
<h3 id="4、代码实现-5"><a href="#4、代码实现-5" class="headerlink" title="4、代码实现"></a>4、代码实现</h3><pre class="line-numbers language-c++"><code class="language-c++">void merge_sort(int q[], int l, int r)
{
    //递归的终止情况
    if(l >= r) return;

    //第一步：分成子问题
    int mid = l + r >> 1;

    //第二步：递归处理子问题
    merge_sort(q, l, mid ), merge_sort(q, mid + 1, r);

    //第三步：合并子问题
    int k = 0, i = l, j = mid + 1, tmp[r - l + 1];
    while(i <= mid && j <= r)
        if(q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    while(i <= mid) tmp[k++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];

    for(k = 0, i = l; i <= r; k++, i++) q[i] = tmp[k];
}<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<p><strong>tmp 保存的是 q[l..mid] , q[mid+1..r] 中从小到大排序的所有数</strong><br>    证明(第一个 <code>while</code> 循环)<br>    循环不变式: <code>tmp[0..k-1]</code> 保存上述俩数组中从小到大排序的最小 <code>k</code> 个数</p>
<p><strong>1.初始</strong></p>
<p>​    <code>k = 0, tmp[0..k-1]</code> 为空，显然成立</p>
<p><strong>2.保持</strong></p>
<p>​    假设某轮循环开始之前，循环不变式成立</p>
<p>​    若 <code>q[i] &lt;= q[j], 则 tmp[k] = q[i]</code></p>
<p>​    其中 <code>q[i] &lt;= q[i+1..mid], q[i] &lt;= q[j] &lt;= q[j+1..r]</code></p>
<p>​    ∴ q[i] 是剩下的所有数中最小的一个</p>
<p>​    当 q[i] &gt; q[j] 时，同理可以得到 <code>tmp[k] = q[j]</code> 是剩下数中最小的一个</p>
<p>​    ∴ <code>tmp[k]</code> 是剩下数中最小的一个</p>
<p>​    ∴ <code>k</code>自增之后，下轮循环开始之前，<code>tmp[0..k-1]</code>保存从小到大排序的最小k个数</p>
<p><strong>3.终止</strong></p>
<p>​    <code>i &gt; mid</code> 或 <code>j &gt; r</code></p>
<p>​    则 <code>q[l..mid]</code> 和 <code>q[mid+1..r]</code> 其中一个数组的数都已遍历</p>
<p>​    <code>tmp[0..k-1]</code>保存从小到大排序的最小k个数</p>
<h2 id="七、计数排序（Counting-Sort）"><a href="#七、计数排序（Counting-Sort）" class="headerlink" title="七、计数排序（Counting Sort）"></a>七、计数排序（Counting Sort）</h2><h3 id="1、原理-6"><a href="#1、原理-6" class="headerlink" title="1、原理"></a>1、原理</h3><p>​    计数排序，又叫非比较排序，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数</p>
<h3 id="2、步骤-6"><a href="#2、步骤-6" class="headerlink" title="2、步骤"></a>2、步骤</h3><ul>
<li>找出待排序的数组中最大和最小的元素；</li>
<li>统计数组中每个值为i的元素出现的次数，存入数组C的第i项；</li>
<li>对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；</li>
<li>反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。</li>
</ul>
<h3 id="3、动画演示-6"><a href="#3、动画演示-6" class="headerlink" title="3、动画演示"></a>3、动画演示</h3><p><img src="https://cdn.jsdelivr.net/gh/MUYIio/CDN@2.1/Images/posts/qSort/7.gif" alt></p>
<h3 id="4、代码实现-6"><a href="#4、代码实现-6" class="headerlink" title="4、代码实现"></a>4、代码实现</h3><pre class="line-numbers language-c++"><code class="language-c++">void counting_sort()
{
    int sorted[N];
    int maxv = a[0];
    for (int i = 1; i < n; i ++ )
        if (maxv < a[i])
            maxv = a[i];
    int count[maxv+1];
    for (int i = 0; i < n; i ++ ) count[a[i]] ++ ;
    for (int i = 1; i <= maxv; i ++ ) count[i] += count[i-1];
    for (int i = n-1; i >= 0; i -- )
    {
        sorted[count[a[i]]-1] = a[i];
        count[a[i]] -- ;
    }
    for (int i = 0; i < n; i ++ ) a[i] = sorted[i];
}<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="八、基数排序（Radix-Sort）"><a href="#八、基数排序（Radix-Sort）" class="headerlink" title="八、基数排序（Radix Sort）"></a>八、基数排序（Radix Sort）</h2><h3 id="1、原理-7"><a href="#1、原理-7" class="headerlink" title="1、原理"></a>1、原理</h3><p>基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。</p>
<h3 id="2、步骤-7"><a href="#2、步骤-7" class="headerlink" title="2、步骤"></a>2、步骤</h3><ul>
<li>取得数组中的最大数，并取得位数；</li>
<li>arr为原始数组，从最低位开始取每个位组成radix数组；</li>
<li>对radix进行计数排序（利用计数排序适用于小范围数的特点)。</li>
</ul>
<h3 id="3、动画演示-7"><a href="#3、动画演示-7" class="headerlink" title="3、动画演示"></a>3、动画演示</h3><p><img src="https://cdn.jsdelivr.net/gh/MUYIio/CDN@2.1/Images/posts/qSort/8.gif" alt></p>
<h3 id="4、代码实现-7"><a href="#4、代码实现-7" class="headerlink" title="4、代码实现"></a>4、代码实现</h3><pre class="line-numbers language-c++"><code class="language-c++">int maxbit()
{
    int maxv = a[0];
    for (int i = 1; i < n; i ++ )
        if (maxv < a[i])
            maxv = a[i];
    int cnt = 1;
    while (maxv >= 10) maxv /= 10, cnt ++ ;

    return cnt;
}
void radixsort()
{
    int t = maxbit();
    int radix = 1;

    for (int i = 1; i <= t; i ++ )
    {
        for (int j = 0; j < 10; j ++ ) count[j] = 0;
        for (int j = 0; j < n; j ++ )
        {
            int k = (a[j] / radix) % 10;
            count[k] ++ ;
        }
        for (int j = 1; j < 10; j ++ ) count[j] += count[j-1];
        for (int j = n-1; j >= 0; j -- )
        {
            int k = (a[j] / radix) % 10;
            temp[count[k]-1] = a[j];
            count[k] -- ;
        }
        for (int j = 0; j < n; j ++ ) a[j] = temp[j];
        radix *= 10;
    }

}
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="九、桶排序（Bucket-Sort）"><a href="#九、桶排序（Bucket-Sort）" class="headerlink" title="九、桶排序（Bucket Sort）"></a>九、桶排序（Bucket Sort）</h2><h3 id="1、原理-8"><a href="#1、原理-8" class="headerlink" title="1、原理"></a>1、原理</h3><p> 遍历原始序列确定最大值 <code>maxval</code> 和最小值 <code>minval</code>，并确定桶的个数 <code>n</code>; 然后，将待排序集合中处于同一个值域的元素存入同一个桶中,在桶内使用各种现有的算法进行排序; 最后按照从小到大的顺序依次收集桶中的每一个元素, 即为最终结果。</p>
<h3 id="2、步骤-8"><a href="#2、步骤-8" class="headerlink" title="2、步骤"></a>2、步骤</h3><ul>
<li>1.设置一个定量的数组当作空桶；</li>
<li>2.遍历输入数据，并且把数据一个一个放到对应的桶里去；</li>
<li>3.对每个不是空的桶进行排序；</li>
<li>4.从不是空的桶里把排好序的数据拼接起来。 </li>
</ul>
<p>桶排序是一种用空间换取时间的排序。桶的个数和大小都是我们人为设置的，而每个桶又要避免空桶的情况，所以我们在使用桶排序的时候即需要对待排序数列要求偏均匀，又要要求桶的设计兼顾效率和空间；数要相对均匀分布，桶的个数也要合理设计。在设计桶排序时，需要知道输入数据的上界和下界。</p>
<h3 id="3、动画演示-8"><a href="#3、动画演示-8" class="headerlink" title="3、动画演示"></a>3、动画演示</h3><p><img src="https://cdn.jsdelivr.net/gh/MUYIio/CDN@2.1/Images/posts/qSort/9.gif" alt></p>
<p><font color="red" size="4"><code>（动图来源于@五分钟学算法，侵删）</code></font></p>
<h3 id="4、代码实现-8"><a href="#4、代码实现-8" class="headerlink" title="4、代码实现"></a>4、代码实现</h3><pre class="line-numbers language-c++"><code class="language-c++">//桶排序 
void BucketSort(int a[], int n){
    int minval = a[0], maxval = a[0];
    for(int i = 0; i < n; i ++){//寻找原序列数组元素的最大值和最小值 
        minval = min(minval, a[i]);
        maxval = max(maxval, a[i]);
    }

    int bnum = 10;//桶中元素个数 
    int m = (maxval - minval) / bnum + 1;//桶的个数 
    vector< vector<int> > bucket(m);

    //收集,将元素入相应的桶中. 减偏移量是为了将元素映射到更小的区间内,省内存 
    for(int i = 0; i < n; i ++) bucket[(a[i] - minval) / bnum].push_back(a[i]);

    //将桶内元素排序 
    for(int i = 0; i < m; i ++) sort(bucket.begin(), bucket.end());

    //收集, 将各个桶中的元素收集到一起 
    for(int i = 0, k = 0; i < m; i ++){
        for(int j = 0; j < bucket[i].size(); j ++){
            data[k ++] = bucket[i][j];
        }
    }
}<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h2 id="十、堆排序（Heap-Sort）"><a href="#十、堆排序（Heap-Sort）" class="headerlink" title="十、堆排序（Heap Sort）"></a>十、堆排序（Heap Sort）</h2><h3 id="1、原理-9"><a href="#1、原理-9" class="headerlink" title="1、原理"></a>1、原理</h3><p>先看看堆的特性：</p>
<blockquote>
<p>堆是一种特殊的树形数据结构，即完全二叉树。堆分为大根堆和小根堆，大根堆为根节点的值大于两个子节点的值；小根堆为根节点的值小于两个子节点的值，同时根节点的两个子树也分别是一个堆。</p>
</blockquote>
<p><img src="https://cdn.jsdelivr.net/gh/MUYIio/CDN@2.1/Images/posts/qSort/12.png" alt></p>
<p>堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。</p>
<h3 id="2、步骤-9"><a href="#2、步骤-9" class="headerlink" title="2、步骤"></a>2、步骤</h3><ul>
<li>1.构建堆：将待排序序列构建成一个堆 H[0……n-1]，从最后一个非叶子结点开始，从左至右，从下至上进行调整。根据升序或降序需求选择大顶堆或小顶堆；</li>
<li>2.此时的堆顶元素，为最大或者最小元素；</li>
<li>3.把堆顶元素和堆尾元素互换，调整堆，重新使堆有序；</li>
<li>4.此时堆顶元素为第二大元素；</li>
<li>5.重复以上步骤，直到堆变空。</li>
</ul>
<h3 id="3、动画演示-9"><a href="#3、动画演示-9" class="headerlink" title="3、动画演示"></a>3、动画演示</h3><p><img src="https://cdn.jsdelivr.net/gh/MUYIio/CDN@2.1/Images/posts/qSort/10.gif" alt></p>
<h3 id="4、代码实现-9"><a href="#4、代码实现-9" class="headerlink" title="4、代码实现"></a>4、代码实现</h3><pre class="line-numbers language-c++"><code class="language-c++">void down(int u)
{
    int t = u;
    if (u<<1 <= n && h[u<<1] < h[t]) t = u<<1;
    if ((u<<1|1) <= n && h[u<<1|1] < h[t]) t = u<<1|1;
    if (u != t)
    {
        swap(h[u], h[t]);
        down(t);
    }
}

int main()
{
    for (int i = 1; i <= n; i ++ ) cin >> h[i];
    for (int i = n/2; i; i -- ) down(i);
    while (true)
    {
        if (!n) break;
        cout << h[1] << ' ';
        h[1] = h[n];
        n -- ;
        down(1);
    }
    return 0;
}<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

            </div>
            <hr />

            
            <style>
    #reward {
        margin: 40px 0;
        text-align: center;
    }

    #reward .reward-link {
        font-size: 1.88rem;
    }

    #reward .btn-floating:hover {
        box-shadow: 0 6px 12px rgba(0, 0, 0, 0.2), 0 5px 15px rgba(0, 0, 0, 0.2);
    }

    #rewardModal {
        width: 320px;
        height: 350px;
    }

    #rewardModal .reward-title {
        margin: 15px auto;
        padding-bottom: 5px;
    }

    #rewardModal .modal-content {
        padding: 10px;
    }

    #rewardModal .close {
        position: absolute;
        right: 15px;
        top: 15px;
        color: rgba(0, 0, 0, 0.5);
        font-size: 1.3rem;
        line-height: 20px;
        cursor: pointer;
    }

    #rewardModal .close:hover {
        color: #ef5350;
        transform: scale(1.3);
        -moz-transform:scale(1.3);
        -webkit-transform:scale(1.3);
        -o-transform:scale(1.3);
    }

    #rewardModal .reward-tabs {
        margin: 0 auto;
        width: 210px;
    }

    .reward-tabs .tabs {
        height: 38px;
        margin: 10px auto;
        padding-left: 0;
    }

    .reward-content ul {
        padding-left: 0 !important;
    }

    .reward-tabs .tabs .tab {
        height: 38px;
        line-height: 38px;
    }

    .reward-tabs .tab a {
        color: #fff;
        background-color: #ccc;
    }

    .reward-tabs .tab a:hover {
        background-color: #ccc;
        color: #fff;
    }

    .reward-tabs .wechat-tab .active {
        color: #fff !important;
        background-color: #22AB38 !important;
    }

    .reward-tabs .alipay-tab .active {
        color: #fff !important;
        background-color: #019FE8 !important;
    }

    .reward-tabs .reward-img {
        width: 210px;
        height: 210px;
    }
</style>

<div id="reward">
    <a href="#rewardModal" class="reward-link modal-trigger btn-floating btn-large waves-effect waves-light red">赏</a>

    <!-- Modal Structure -->
    <div id="rewardModal" class="modal">
        <div class="modal-content">
            <a class="close modal-close"><i class="fa fa-close"></i></a>
            <h4 class="reward-title">写作不易，客官能否打赏一杯奶茶？</h4>
            <div class="reward-content">
                <div class="reward-tabs">
                    <ul class="tabs row">
                        <li class="tab col s6 alipay-tab waves-effect waves-light"><a href="#alipay">支付宝</a></li>
                        <li class="tab col s6 wechat-tab waves-effect waves-light"><a href="#wechat">微 信</a></li>
                    </ul>
                    <div id="alipay">
                        <img src="https://cdn.jsdelivr.net/gh/MUYIio/CDN@1.2/Images/reward/alipay.jpg" class="reward-img" alt="支付宝打赏二维码">
                    </div>
                    <div id="wechat">
                        <img src="https://cdn.jsdelivr.net/gh/MUYIio/CDN@1.2/Images/reward/wechat.jpg" class="reward-img" alt="微信打赏二维码">
                    </div>
                </div>
            </div>
        </div>
    </div>
</div>

<script>
    $(function () {
        $('.tabs').tabs();
    });
</script>
            

            <link rel="stylesheet" type="text/css" href="/libs/share/css/share.min.css">

<div id="article-share">
    
    <div class="social-share" data-disabled="qzone" data-wechat-qrcode-helper="<p>微信里点“发现”->“扫一扫”二维码便可查看分享。</p>"></div>
    
</div>

<script src="/libs/share/js/social-share.min.js"></script>

            

    <div class="reprint" id="reprint-statement">
        <p class="reprint-tip">
            <i class="fa fa-exclamation-triangle"></i>&nbsp;&nbsp;
            <span>转载规则</span>
        </p>
        
            <div class="center-align">
                <a rel="license" href="https://creativecommons.org/licenses/by/4.0/deed.zh">
                    <img alt=""
                         style="border-width:0"
                         src="https://i.creativecommons.org/l/by/4.0/88x31.png"/>
                </a>
            </div>
            <br/>
            <span xmlns:dct="http://purl.org/dc/terms/" href="http://purl.org/dc/dcmitype/Text"
                  property="dct:title" rel="dct:type">
                    《十大经典排序算法(附动画及代码)》
                </span> 由
            <a xmlns:cc="http://creativecommons.org/ns#" href="/shi-da-jing-dian-pai-xu-suan-fa-fu-dong-hua-ji-dai-ma.html" property="cc:attributionName"
               rel="cc:attributionURL">
                Tyzhao
            </a> 采用
            <a rel="license" href="https://creativecommons.org/licenses/by/4.0/deed.zh">
                知识共享署名 4.0 国际许可协议
            </a>进行许可。
        
    </div>

    <script async defer>
      document.addEventListener("copy", function (e) {
        let toastHTML = '<span>复制成功，请遵循本文的转载规则</span><button class="btn-flat toast-action" onclick="navToReprintStatement()" style="font-size: smaller">查看</a>';
        M.toast({html: toastHTML})
      });

      function navToReprintStatement() {
        $("html, body").animate({scrollTop: $("#reprint-statement").offset().top - 80}, 800);
      }
    </script>


        </div>
    </div>

    
    <link rel="stylesheet" href="/libs/gitalk/gitalk.css">
<link rel="stylesheet" href="/css/my-gitalk.css">

<div class="card gitalk-card" data-aos="fade-up">
    <div id="gitalk-container" class="card-content"></div>
</div>

<script src="/libs/gitalk/gitalk.min.js"></script>
<script>
    let gitalk = new Gitalk({
        clientID: '46697bb9a799731534b2',
        clientSecret: 'b4f73ab06fb0a67da32d620ebc395111f2d508ee',
        repo: 'muyiio.github.io',
        owner: 'MUYIio',
        admin: "MUYIio",
        id: 'shi-da-jing-dian-pai-xu-suan-fa-fu-dong-hua-ji-dai-ma.html',
        distractionFreeMode: false  // Facebook-like distraction free mode
    });

    gitalk.render('gitalk-container');
</script>
    

    

    

    

    
    <style>
    .valine-card {
        margin: 1.5rem auto;
    }

    .valine-card .card-content {
        padding: 20px 20px 5px 20px;
    }

    #vcomments input[type=text],
    #vcomments input[type=email],
    #vcomments input[type=url],
    #vcomments textarea {
        box-sizing: border-box;
    }

    #vcomments p {
        margin: 2px 2px 10px;
        font-size: 1.05rem;
        line-height: 1.78rem;
    }

    #vcomments blockquote p {
        text-indent: 0.2rem;
    }

    #vcomments a {
        padding: 0 2px;
        color: #42b983;
        font-weight: 500;
        text-decoration: underline;
    }

    #vcomments img {
        max-width: 100%;
        height: auto;
        cursor: pointer;
    }

    #vcomments ol li {
        list-style-type: decimal;
    }

    #vcomments ol,
    ul {
        display: block;
        padding-left: 2em;
        word-spacing: 0.05rem;
    }

    #vcomments ul li,
    ol li {
        display: list-item;
        line-height: 1.8rem;
        font-size: 1rem;
    }

    #vcomments ul li {
        list-style-type: disc;
    }

    #vcomments ul ul li {
        list-style-type: circle;
    }

    #vcomments table, th, td {
        padding: 12px 13px;
        border: 1px solid #dfe2e5;
    }

    #vcomments table, th, td {
        border: 0;
    }

    table tr:nth-child(2n), thead {
        background-color: #fafafa;
    }

    #vcomments table th {
        background-color: #f2f2f2;
        min-width: 80px;
    }

    #vcomments table td {
        min-width: 80px;
    }

    #vcomments h1 {
        font-size: 1.85rem;
        font-weight: bold;
        line-height: 2.2rem;
    }

    #vcomments h2 {
        font-size: 1.65rem;
        font-weight: bold;
        line-height: 1.9rem;
    }

    #vcomments h3 {
        font-size: 1.45rem;
        font-weight: bold;
        line-height: 1.7rem;
    }

    #vcomments h4 {
        font-size: 1.25rem;
        font-weight: bold;
        line-height: 1.5rem;
    }

    #vcomments h5 {
        font-size: 1.1rem;
        font-weight: bold;
        line-height: 1.4rem;
    }

    #vcomments h6 {
        font-size: 1rem;
        line-height: 1.3rem;
    }

    #vcomments p {
        font-size: 1rem;
        line-height: 1.5rem;
    }

    #vcomments hr {
        margin: 12px 0;
        border: 0;
        border-top: 1px solid #ccc;
    }

    #vcomments blockquote {
        margin: 15px 0;
        border-left: 5px solid #42b983;
        padding: 1rem 0.8rem 0.3rem 0.8rem;
        color: #666;
        background-color: rgba(66, 185, 131, .1);
    }

    #vcomments pre {
        font-family: monospace, monospace;
        padding: 1.2em;
        margin: .5em 0;
        background: #272822;
        overflow: auto;
        border-radius: 0.3em;
        tab-size: 4;
    }

    #vcomments code {
        font-family: monospace, monospace;
        padding: 1px 3px;
        font-size: 0.92rem;
        color: #e96900;
        background-color: #f8f8f8;
        border-radius: 2px;
    }

    #vcomments pre code {
        font-family: monospace, monospace;
        padding: 0;
        color: #e8eaf6;
        background-color: #272822;
    }

    #vcomments pre[class*="language-"] {
        padding: 1.2em;
        margin: .5em 0;
    }

    #vcomments code[class*="language-"],
    pre[class*="language-"] {
        color: #e8eaf6;
    }

    #vcomments [type="checkbox"]:not(:checked), [type="checkbox"]:checked {
        position: inherit;
        margin-left: -1.3rem;
        margin-right: 0.4rem;
        margin-top: -1px;
        vertical-align: middle;
        left: unset;
        visibility: visible;
    }

    #vcomments b,
    strong {
        font-weight: bold;
    }

    #vcomments dfn {
        font-style: italic;
    }

    #vcomments small {
        font-size: 85%;
    }

    #vcomments cite {
        font-style: normal;
    }

    #vcomments mark {
        background-color: #fcf8e3;
        padding: .2em;
    }

    #vcomments table, th, td {
        padding: 12px 13px;
        border: 1px solid #dfe2e5;
    }

    table tr:nth-child(2n), thead {
        background-color: #fafafa;
    }

    #vcomments table th {
        background-color: #f2f2f2;
        min-width: 80px;
    }

    #vcomments table td {
        min-width: 80px;
    }

    #vcomments [type="checkbox"]:not(:checked), [type="checkbox"]:checked {
        position: inherit;
        margin-left: -1.3rem;
        margin-right: 0.4rem;
        margin-top: -1px;
        vertical-align: middle;
        left: unset;
        visibility: visible;
    }
</style>

<div class="card valine-card" data-aos="fade-up">
    <div id="vcomments" class="card-content"></div>
</div>

<script src="/libs/valine/av-min.js"></script>
<script src="/libs/valine/Valine.min.js"></script>
<!-- <script src="//unpkg.com/valine@latest/dist/Valine.min.js"></script> -->

<script>
    new Valine({
        el: '#vcomments',
        appId: '2XytdtE76cEw5tyzKupUSM2s-gzGzoHsz',
        appKey: 'CFpPusBW6xLPhs8OQUaCkX2c',
        notify: 'true' === 'true',
        verify: 'false' === 'true',
        visitor: 'false' === 'true',
        avatar: 'wavatar',
        pageSize: '10',
        lang: 'zh-cn',
        placeholder: '如果你没有GitHub账号，还可以在这里评论啦！'
    });
</script>

    

    

<article id="prenext-posts" class="prev-next articles">
    <div class="row article-row">
        
        <div class="article col s12 m6" data-aos="fade-up" data-aos="fade-up">
            <div class="article-badge left-badge text-color">
                <i class="fa fa-dot-circle-o"></i>&nbsp;本篇
            </div>
            <div class="card">
                <a href="/shi-da-jing-dian-pai-xu-suan-fa-fu-dong-hua-ji-dai-ma.html">
                    <div class="card-image">
                        
                        
                        <img src="https://cdn.jsdelivr.net/gh/MUYIio/CDN@1.2/Images/featureimages/24.jpg" class="responsive-img" alt="十大经典排序算法(附动画及代码)">
                        
                        <span class="card-title">十大经典排序算法(附动画及代码)</span>
                    </div>
                </a>
                <div class="card-content article-content">
                    <div class="summary block-with-text">
                        
                            关于各种排序算法的笔记总结，含代码展示和动画演示！
                        
                    </div>
                    <div class="publish-info">
                            <span class="publish-date">
                                <i class="fa fa-clock-o fa-fw icon-date"></i>2021-12-14
                            </span>
                        <span class="publish-author">
                            
                            <i class="fa fa-bookmark fa-fw icon-category"></i>
                            
                            <a href="/categories/算法/" class="post-category" target="_blank">
                                    算法
                                </a>
                            
                            <a href="/categories/算法/C/" class="post-category" target="_blank">
                                    C++
                                </a>
                            
                            
                        </span>
                    </div>
                </div>

                
                <div class="card-action article-tags">
                    
                    <a href="/tags/排序/" target="_blank">
                        <span class="chip bg-color">排序</span>
                    </a>
                    
                </div>
                
            </div>
        </div>
        
        
        <div class="article col s12 m6" data-aos="fade-up">
            <div class="article-badge right-badge text-color">
                下一篇&nbsp;<i class="fa fa-chevron-right"></i>
            </div>
            <div class="card">
                <a href="/shi-yong-java-arrays-lei-jin-xing-pai-xu.html">
                    <div class="card-image">
                        
                        
                        <img src="https://cdn.jsdelivr.net/gh/MUYIio/CDN@1.2/Images/featureimages/14.jpg" class="responsive-img" alt="使用Java Arrays类进行排序">
                        
                        <span class="card-title">使用Java Arrays类进行排序</span>
                    </div>
                </a>
                <div class="card-content article-content">
                    <div class="summary block-with-text">
                        
                            C语言有qsort()函数，C++有sort()函数，java语言有Arrays类（与Array区分）
                        
                    </div>
                    <div class="publish-info">
                            <span class="publish-date">
                                <i class="fa fa-clock-o fa-fw icon-date"></i>2021-10-21
                            </span>
                        <span class="publish-author">
                            
                            <i class="fa fa-bookmark fa-fw icon-category"></i>
                            
                            <a href="/categories/Java/" class="post-category" target="_blank">
                                    Java
                                </a>
                            
                            
                        </span>
                    </div>
                </div>
                
                <div class="card-action article-tags">
                    
                    <a href="/tags/排序/" target="_blank">
                        <span class="chip bg-color">排序</span>
                    </a>
                    
                </div>
                
            </div>
        </div>
        
    </div>
</article>
</div>


<script>
    $('#articleContent').on('copy', function (e) {
        // IE8 or earlier browser is 'undefined'
        if (typeof window.getSelection === 'undefined') return;

        var selection = window.getSelection();
        // if the selection is short let's not annoy our users.
        if (('' + selection).length < Number.parseInt('120')) {
            return;
        }

        // create a div outside of the visible area and fill it with the selected text.
        var bodyElement = document.getElementsByTagName('body')[0];
        var newdiv = document.createElement('div');
        newdiv.style.position = 'absolute';
        newdiv.style.left = '-99999px';
        bodyElement.appendChild(newdiv);
        newdiv.appendChild(selection.getRangeAt(0).cloneContents());

        // we need a <pre> tag workaround.
        // otherwise the text inside "pre" loses all the line breaks!
        if (selection.getRangeAt(0).commonAncestorContainer.nodeName === 'PRE') {
            newdiv.innerHTML = "<pre>" + newdiv.innerHTML + "</pre>";
        }

        var url = document.location.href;
        newdiv.innerHTML += '<br />'
            + '来源: Shawlon`s Blog<br />'
            + '作者: Tyzhao<br />'
            + '链接: <a href="' + url + '">' + url + '</a><br />'
            + '本文章著作权归作者所有，任何形式的转载都请注明出处。';

        selection.selectAllChildren(newdiv);
        window.setTimeout(function () { bodyElement.removeChild(newdiv); }, 200);
    });
</script>

    </div>
    <div id="toc-aside" class="expanded col l3 hide-on-med-and-down">
        <div class="toc-widget">
            <div class="toc-title"><i class="fa fa-list-alt"></i>&nbsp;&nbsp;目录</div>
            <div id="toc-content"></div>
        </div>
    </div>
</div>

<!-- TOC 悬浮按钮. -->

<div id="floating-toc-btn" class="hide-on-med-and-down">
    <a class="btn-floating btn-large bg-color">
        <i class="fa fa-list"></i>
    </a>
</div>


<script src="/libs/tocbot/tocbot.min.js"></script>
<script>
    $(function () {
        tocbot.init({
            tocSelector: '#toc-content',
            contentSelector: '#articleContent',
            headingsOffset: -($(window).height() * 0.4 - 45),
            // headingsOffset: -205,
            headingSelector: 'h1, h2, h3, h4'
        });

        // modify the toc link href to support Chinese.
        let i = 0;
        let tocHeading = 'toc-heading-';
        $('#toc-content a').each(function () {
            $(this).attr('href', '#' + tocHeading + (++i));
        });

        // modify the heading title id to support Chinese.
        i = 0;
        $('#articleContent').children('h1, h2, h3, h4').each(function () {
            $(this).attr('id', tocHeading + (++i));
        });

        // Set scroll toc fixed.
        let tocHeight = parseInt($(window).height() * 0.4 - 64);
        let $tocWidget = $('.toc-widget');
        $(window).scroll(function () {
            let scroll = $(window).scrollTop();
            /* add post toc fixed. */
            if (scroll > tocHeight) {
                $tocWidget.addClass('toc-fixed');
            } else {
                $tocWidget.removeClass('toc-fixed');
            }
        });

        
        /* 修复文章卡片 div 的宽度. */
        let fixPostCardWidth = function (srcId, targetId) {
            let srcDiv = $('#' + srcId);
            if (srcDiv.length === 0) {
                return;
            }

            let w = srcDiv.width();
            if (w >= 450) {
                w = w + 21;
            } else if (w >= 350 && w < 450) {
                w = w + 18;
            } else if (w >= 300 && w < 350) {
                w = w + 16;
            } else {
                w = w + 14;
            }
            $('#' + targetId).width(w);
        };

        // 切换TOC目录展开收缩的相关操作.
        const expandedClass = 'expanded';
        let $tocAside = $('#toc-aside');
        let $mainContent = $('#main-content');
        $('#floating-toc-btn .btn-floating').click(function () {
            if ($tocAside.hasClass(expandedClass)) {
                $tocAside.removeClass(expandedClass).slideUp(500);
                $mainContent.removeClass('l9');
            } else {
                $tocAside.addClass(expandedClass).slideDown(500);
                $mainContent.addClass('l9');
            }
            fixPostCardWidth('artDetail', 'prenext-posts');
        });
        
    });
</script>
    

</main>


<script src="https://cdn.bootcss.com/mathjax/2.7.5/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<script>
    MathJax.Hub.Config({
        tex2jax: {inlineMath: [['$', '$'], ['\(', '\)']]}
    });
</script>

<script type="text/javascript" src="/libs/codeBlock/codeBlockFuction.js"></script>
<!-- 代码语言 -->
<script type="text/javascript" src="/libs/codeBlock/codeLang.js"></script>
<!-- 代码块复制 -->
<script type="text/javascript" src="/libs/codeBlock/codeCopy.js"></script>
<script type="text/javascript" src="/libs/codeBlock/clipboard.min.js"></script>
<!-- 代码块收缩 -->
<script type="text/javascript" src="/libs/codeBlock/codeShrink.js"></script> 
<!-- 代码块折行 -->
<style type="text/css">code[class*="language-"], pre[class*="language-"] { white-space: pre !important; }</style>


    <footer class="page-footer bg-color">
    <div class="container row center-align">
       <div class="Copy-right">
            &copy; 2021 Yshawlon. All Rights Reserved.

           <img src="https://cdn.jsdelivr.net/gh/MUYIio/CDN@1.2/Images/avatars/icp.png" style="width:18px;height:18px;margin-bottom:-2px" alt="ICP">
           <a href="https://beian.miit.gov.cn/#/Integrated/index" target="_blank">渝ICP备2020014220号-1</a>丨
           <img src="https://cdn.jsdelivr.net/gh/MUYIio/CDN@1.2/Images/avatars/moeicp.png" style="width:18px;height:18px;margin-bottom:-3px" alt="MOE ICP">
           <a href="https://icp.gov.moe/" target="_blank">萌ICP备20216999号</a>丨            
           <!--<a href="/sitemap.xml" target="_blank">站点地图</a>丨-->
           
            &nbsp;<i class="fa fa-area-chart"></i>&nbsp;站点总字数:&nbsp;
            <span class="white-color">72.3k
             丨            
            <a href="https://tongji.baidu.com/web/welcome/ico?s=df42dpc7224a5f6a8d435" target="_blank">百度统计</a>丨
           <script type="text/javascript">document.write(unescape("%3Cspan id='cnzz_stat_icon_1278720284'%3E%3C/span%3E%3Cscript src='https://s9.cnzz.com/z_stat.php%3Fid%3D1278720284%26show%3Dpic' type='text/javascript'%3E%3C/script%3E"));</script>

            <span id="sitetime"></span>

            
            
            
            
            <span id="busuanzi_container_site_pv" style='display:none'>
                <i class="fa fa-users"></i>
                本站总访问量 <span id="busuanzi_value_site_pv" class="red-color"></span>
            </span>
            
            
            <span id="busuanzi_container_site_uv" style='display:none'>
               人次,&nbsp;<i class="fa fa-user"></i>访客数 <span id="busuanzi_value_site_uv" class="blue-color"></span> 人.
            </span>
            
            
        </div>        
        <div class="social-link social-statis">
    <a href="https://github.com/MUYIio" class="tooltipped" target="_blank" data-tooltip="访问我的GitHub" data-position="top" data-delay="50">
        <i class="fa fa-github"></i>
    </a>



    <a href="https://www.csdn.net/weixin_45682081" class="tooltipped" target="_blank" data-tooltip="访问我的CSDN主页" data-position="top" data-delay="50">
        <i class="fa fa-codiepie"></i>
    </a>



    <a href="https://www.zhihu.com/zhihu.com/people/muyiio" class="tooltipped" target="_blank" data-tooltip="访问我的知乎" data-position="top" data-delay="50">
        <i class="fa fa-inverse">知</i>
    </a>



    <a href="https://user.qzone.qq.com/1571504536" class="tooltipped" target="_blank" data-tooltip="访问我的QQ空间" data-position="top" data-delay="50">
        <i class="fa fa-qq"></i>
    </a>



    <a href="mailto:1571504536@qq.com" class="tooltipped" target="_blank" data-tooltip="邮件联系我" data-position="top" data-delay="50">
        <i class="fa fa-envelope-open"></i>
    </a>



    <a href="/atom.xml" class="tooltipped" target="_blank" data-tooltip="RSS 订阅" data-position="top" data-delay="50">
        <i class="fa fa-rss"></i>
    </a>
</div>


    </div>
    <div class="container row center-align">
    <div class="github-badge">
      <a style="color: #fff" rel="license" href="https://hexo.io/" target="_blank" title="由 Hexo 强力驱动">
      <span class="badge-subject">Powered</span><span class="badge-value bg-blue">Hexo</span></a>
    </div>
    <div class="github-badge">
      <a style="color: #fff" rel="license" href="https://github.com/" target="_blank" title="静态网页托管于 GitHub Pages 和 Coding Pages">
      <span class="badge-subject">Hosted</span><span class="badge-value bg-brightgreen">GitHub & Coding</span></a>
    </div>
    <div class="github-badge">
      <a style="color: #fff" rel="license" href="https://www.cloud.tencent.com/" target="_blank" title="腾讯云提供域名相关服务">
      <span class="badge-subject">DNS</span><span class="badge-value bg-blueviolet">Tencent cloud</span></a>
    </div>
    <div class="github-badge">
      <a style="color: #fff" rel="license" href="https://www.jsdelivr.com/" target="_blank" title="jsDelivr 提供 CDN 加速服务">
      <span class="badge-subject">CDN</span><span class="badge-value bg-orange">jsDelivr</span></a>
    </div>
    <div class="github-badge">
        <a style="color: #fff" rel="license" href="https://github.com/blinkfox/hexo-theme-matery/" target="_blank" title="站点使用 Matery 主题">
      <span class="badge-subject">Theme</span><span class="badge-value bg-blue">Matery</span></a>
    </div>
    <div class="github-badge">
      <a style="color: #fff" rel="license" href="http://creativecommons.org/licenses/by-nc-sa/4.0/" target="_blank" title="本站点采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可">
      <span class="badge-subject"><i class="fa fa-copyright"></i></span><span class="badge-value bg-lightgrey">BY-NC-SA 4.0</span></a>
    </div>
    <div class="github-badge">
      <a style="color: #fff" rel="license" href="https://996.icu/" target="_blank" title="支持 996.ICU">
      <span class="badge-subject">Link</span><span class="badge-value bg-red">996.ICU</span></a>
    </div>
    <div class="github-badge">
      <span class="badge-subject">WordCount</span><span class="badge-value bg-blueviolet">72.3k</span>
    </div>
</footer>

<div class="progress-bar"></div>

<!-- 不蒜子计数初始值纠正 -->
<script>
    $(document).ready(function () {

        var int = setInterval(fixCount, 50);
        var pvcountOffset = 80000;
        var uvcountOffset = 20000;

        function fixCount() {
            if (document.getElementById("busuanzi_container_site_pv").style.display != "none") {
                $("#busuanzi_value_site_pv").html(parseInt($("#busuanzi_value_site_pv").html()) + pvcountOffset);
                clearInterval(int);
            }
            if ($("#busuanzi_container_site_pv").css("display") != "none") {
                $("#busuanzi_value_site_uv").html(parseInt($("#busuanzi_value_site_uv").html()) + uvcountOffset); // 加上初始数据 
                clearInterval(int);
            }
        }
    });
</script>

<script language=javascript>
    function siteTime() {
        window.setTimeout("siteTime()", 1000);
        var seconds = 1000;
        var minutes = seconds * 60;
        var hours = minutes * 60;
        var days = hours * 24;
        var years = days * 365;
        var today = new Date();
        var todayYear = today.getFullYear();
        var todayMonth = today.getMonth() + 1;
        var todayDate = today.getDate();
        var todayHour = today.getHours();
        var todayMinute = today.getMinutes();
        var todaySecond = today.getSeconds();
        /* Date.UTC() -- 返回date对象距世界标准时间(UTC)1970年1月1日午夜之间的毫秒数(时间戳)
        year - 作为date对象的年份，为4位年份值
        month - 0-11之间的整数，做为date对象的月份
        day - 1-31之间的整数，做为date对象的天数
        hours - 0(午夜24点)-23之间的整数，做为date对象的小时数
        minutes - 0-59之间的整数，做为date对象的分钟数
        seconds - 0-59之间的整数，做为date对象的秒数
        microseconds - 0-999之间的整数，做为date对象的毫秒数 */
        var t1 = Date.UTC(2020, 01, 01, 00, 00, 00); //北京时间2018-2-13 00:00:00
        var t2 = Date.UTC(todayYear, todayMonth, todayDate, todayHour, todayMinute, todaySecond);
        var diff = t2 - t1;
        var diffYears = Math.floor(diff / years);
        var diffDays = Math.floor((diff / days) - diffYears * 365);
        var diffHours = Math.floor((diff - (diffYears * 365 + diffDays) * days) / hours);
        var diffMinutes = Math.floor((diff - (diffYears * 365 + diffDays) * days - diffHours * hours) / minutes);
        var diffSeconds = Math.floor((diff - (diffYears * 365 + diffDays) * days - diffHours * hours - diffMinutes * minutes) / seconds);
        document.getElementById("sitetime").innerHTML = " | 本站已运行 " + diffYears + " 年 " + diffDays + " 天 " + diffHours + " 小时 " + diffMinutes + " 分钟 " + diffSeconds + " 秒";
    }/*因为建站时间还没有一年，就将之注释掉了。需要的可以取消*/
    siteTime();
</script>

    <!-- 搜索遮罩框 -->
<div id="searchModal" class="modal">
    <div class="modal-content">
        <div class="search-header">
            <span class="title"><i class="fa fa-search"></i>&nbsp;&nbsp;搜索</span>
            <input type="search" id="searchInput" name="s" placeholder="请输入搜索的关键字"
                   class="search-input">
        </div>
        <div id="searchResult"></div>
    </div>
</div>

<script src="/js/search.js"></script>
<script type="text/javascript">
$(function () {
    searchFunc("/" + "search.xml", 'searchInput', 'searchResult');
});
</script>
    <!-- 回到顶部按钮 -->
<div id="backTop" class="top-scroll">
    <a class="btn-floating btn-large waves-effect waves-light" href="#!">
        <i class="fa fa-angle-up"></i>
    </a>
</div>


    <script src="/libs/materialize/materialize.min.js"></script>
    <script src="/libs/masonry/masonry.pkgd.min.js"></script>
    <script src="/libs/aos/aos.js"></script>
    <script src="/libs/scrollprogress/scrollProgress.min.js"></script>
    <script src="/libs/lightGallery/js/lightgallery-all.min.js"></script>
    <script src="/js/matery.js"></script>

    <script type="text/javascript"> var OriginTitile = document.title, st; document.addEventListener("visibilitychange", function () { document.hidden ? (document.title = "Σ(っ °Д °;)っ喔哟，崩溃啦！", clearTimeout(st)) : (document.title = "φ(゜▽゜*)♪咦，又好了！", st = setTimeout(function () { document.title = OriginTitile }, 3e3)) })
    </script>

    <!-- Global site tag (gtag.js) - Google Analytics -->

<script async src="https://www.googletagmanager.com/gtag/js?id="></script>
<script>
    window.dataLayer = window.dataLayer || [];
    function gtag() {
        dataLayer.push(arguments);
    }

    gtag('js', new Date());
    gtag('config', '');
</script>



    <!--鼠标点击特效-->
    


    <!--不蒜子计数-->
    
    <script async src="/libs/others/busuanzi.pure.mini.js"></script>
    


    <!-- 雪花特效 -->
    
    
    <!--动态线条背景-->
    <script type="text/javascript"
    color="220,220,220" opacity='0.7' zIndex="-2" count="200" src="//cdn.bootcss.com/canvas-nest.js/1.0.0/canvas-nest.min.js">
    </script>

    <!--鼠标跟随樱花特效 -->
    
        <script type="text/javascript" src="/js/fairyDustCursor.js"></script>
    



    <!--单击显示文字-->
    

    <!--鼠标点击粒子特效-->
    
    <canvas class="fireworks" style="position: fixed;left: 0;top: 0;z-index: 1; pointer-events: none;" ></canvas> 
    <script type="text/javascript" src="//cdn.bootcss.com/animejs/2.2.0/anime.min.js"></script> 
    <script type="text/javascript" src="/js/fireworks.js"></script>
    

    <script async src =“ https://www.jsdelivr.com/terms/acceptable-use-policy-jsdelivr-net ”>
    </script>


    <!--自定义看板娘-->
    <!-- <script src="https://cdn.jsdelivr.net/npm/jquery/dist/jquery.min.js"></script>  -->
    <script src="/live2d-widget/autoload.js"></script>
    <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/font-awesome/css/font-awesome.min.css"/>


</body>
</html>